#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

// 一个固定容量大小的背包，给定两个数组，一个数组代表所占大小，一个数组代表价值，求出所带价值最大的解决方案

vector<int> bestVec, tmpVec;
size_t maxVal{}, totalVal{36}, size{}, price{}, cnt{};

void resolve1(const vector<int> &capVec, const vector<int> &priVec, int i, int len, size_t cap)
{
    if(i == len){
        cnt++;
        if(size <= cap && price > maxVal){
            maxVal = price;
            bestVec = tmpVec;
        }
    }else{
        tmpVec.push_back(capVec[i]);
        size += capVec[i];
        price += priVec[i];
        resolve1(capVec, priVec, i + 1, len, cap);
        tmpVec.pop_back();
        size -= capVec[i];
        price -= priVec[i];

        resolve1(capVec, priVec, i + 1, len, cap);
    }
}

void resolve2(const vector<int> &capVec, const vector<int> &priVec, int i, int len, size_t cap)
{
    if(i == len){
        cnt++;
        if(size <= cap && price > maxVal){
            maxVal = price;
            bestVec = tmpVec;
        }
    }else{
        // 当期背包大小小于最大容量时，才继续向下寻解
        totalVal -= priVec[i];
        if(size + capVec[i] <= cap){
            tmpVec.push_back(capVec[i]);
            size += capVec[i];
            price += priVec[i];
            resolve2(capVec, priVec, i + 1, len, cap);
            tmpVec.pop_back();
            size -= capVec[i];
            price -= priVec[i];
        }

        // 如果当前价值加上剩下的价值小于当前最大值，就不用继续向下递归寻找了
        if(totalVal + price > maxVal){
            resolve2(capVec, priVec, i + 1, len, cap);
        }
        totalVal += priVec[i];
    }
}

int main(int args, char *argv[])
{
    resolve2({11, 3, 1, 4, 5, 2, 10}, {20, 2, 1, 3, 4, 1, 5}, 0, 7, 30);

    for(int i: bestVec){
        cout << i << " ";
    }
    cout << " ,剪枝的子集树叶子结点的个数：" << cnt << endl;

    return 0;
}